// 问题 A: 【数据结构7-4】由先序和中序恢复二叉树
// 时间限制: 1 Sec  内存限制: 128 MB
// 提交: 2520  解决: 526
// [提交][状态][论坛]
// 题目描述
// 1．输入二叉树结点数，先序遍历序列，中序遍历序列

// 2．输出该二叉树的后序遍历序列

// 输入
// 运行界面如下（红色为输入，蓝色为输出）：

// 10

// ABDGCEFHJI

// DGBAECJHFI

// GDBEJHIFCA

// 输出
// 样例输入
// 10
// ABDGCEFHJI
// DGBAECJHFI
// 样例输出
// GDBEJHIFCA
// 提示
#include<stdio.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

typedef struct BiNode {
    char data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

int create(BiTree &T, char pa[], int low_a, int high_a, char pb[], int low_b, int high_b) {
    //创建根结点，递归创建T->lchild,T->rchild
    // @@1
    T = (BiNode *) malloc(sizeof(BiNode));
    int root_pos_a = low_a;
    char root = pa[root_pos_a];
    T->data = root;

    //中序序列中子树的根元素的位置
    int root_pos_b = -1;
    for (int i = low_b; i <= high_b; i++) {
        if (pb[i] == root) {
            root_pos_b = i;
            break;
        }
    }

    //当前左子树的元素的个数
    int leftChildTreeNodeCount = root_pos_b - low_b;
    //当前右子树的元素的个数
    int rightChildTreeNodeCount = high_b - root_pos_b;

    //左子树递归
    if (leftChildTreeNodeCount == 0) {
        T->lchild = NULL;
    } else {create(T->lchild, pa, low_a + 1, low_a + leftChildTreeNodeCount, pb, low_b, root_pos_b - 1);
    }

    //右子树递归
    if (rightChildTreeNodeCount == 0) {
       T->rchild = NULL;
    } else {
        create(T->rchild, pa, low_a + leftChildTreeNodeCount + 1, high_a, pb, root_pos_b + 1, high_b);
    }

    return 1;
    // @@1
}

int CreateBiTree(BiTree &T, int n) {
    //读入先序，中序序列，分别存入数组pa，pb
    char pa[100], pb[100];
    scanf("%s", pa);
    scanf("%s", pb);
    create(T, pa, 0, n - 1, pb, 0, n - 1); //调用create函数创建二叉树T
    return 1;
}

int Postorder(BiTree T) //后序遍历
{
    // @@3
    if (T != NULL) {
        Postorder(T->lchild);
        Postorder(T->rchild);
        printf("%c", T->data);
    }
    return 0;
    // @@3
}

int main() {
    BiTree T;
    int n;

    cin >> n; //二叉树结点个数

    CreateBiTree(T, n); //创建二叉链表

    Postorder(T); //后序遍历

    return 1;
}

